package structure.algorithm.sort;

/**
 * 冒泡排序原理
 * 1.将数组中第一个值与之后的值比较，保留最小的值，并将这个值放在最前面
 * 2.再将数组中第二个值与之后的值比较，保留最小的值，并将这个值放在数组中第二个元素的位置
 * 3.以此类推，直至最后一个值
 * @author fidel
 */
public class BubbleSort {
    private static boolean changed = false;

    /**
     * 一维数组排序
     * @param array
     */
    public static void sort(int[] array) {
        for (int x = 0; x < array.length; x++) {
            for (int y = x + 1; y < array.length; y++) {
                // 如果第一个数大于第二个数，那么将它们的位置调换
                if (array[x] > array[y]) {
                    if (!changed) {
                        changed = true;
                    }
                    int z = array[x];
                    array[x] = array[y];
                    array[y] = z;
                }
            }
            // 如果该数组中所有数的位置都没有变化（即：数组中的所有数已经按照从小到大的顺序排列）
            if (!changed) {
                // 不再进行此数组的排序操作
                break;
            }
        }
        // 将changed的值初始化为false
        changed = false;
    }

    /**
     * 二维数组排序
     * @param array
     */
    public static void sort(int[][] array) {
        for (int a = 0; a < array.length; a++) {
            for (int b = 0; b < array[a].length; b++) {
                for (int c = b + 1; c < array[a].length; c++) {
                    if (array[a][b] > array[a][c]) {
                        if (!changed) {
                            changed = true;
                        }
                        int d = array[a][b];
                        array[a][b] = array[a][c];
                        array[a][c] = d;
                    }
                }
                // 如果该数组中所有数的位置都没有变化
                if (!changed) {
                    // 不再进行此数组的排序操作
                    break;
                }
            }
        }
        changed = false;
    }
}
